using System;
using System.Collections.Generic;
using System.Collections;
using Microsoft.Xna.Framework;
using System.Text;

namespace Campus
{
    public class PathFinder
    {
        #region Fields and Properties

        private World m_parent;

        private Node[,] m_graph;
        private List<Terrain> m_unwalkableTerrain;

        private int m_rows;
        private int m_columns;

        private bool[,] m_walls;

        #endregion

        #region Constructors

        public PathFinder(World parent, List<Terrain> unwalkableTerrainTypes)
        {
            m_parent = parent;
            m_unwalkableTerrain = unwalkableTerrainTypes;
            m_rows = m_parent.TerrainGrid.GetLength(0);    // Y dimension
            m_columns = m_parent.TerrainGrid.GetLength(1);     // X dimension

            DefineSettings(m_parent.TerrainGrid);
        }

        #endregion

        #region Other Functions

        /// <summary>
        /// Determines if the provided position exists in the pathfinder.
        /// </summary>
        /// <param name="row">The row to check.</param>
        /// <param name="column">The column to check.</param>
        /// <returns>True if the position exists in the pathfinder.</returns>
        private bool PointExists(int row, int column)
        {
            if (row < m_rows && row >= 0 && column < m_columns && column >= 0)
                return true;

            return false;
        }

        private void DefineSettings(List<Terrain>[,] terrainGrid)
        {
            // Determine walls
            m_walls = new bool[m_rows, m_columns];

            for (int r = 0; r < m_rows; r++)
            {
                for (int c = 0; c < m_columns; c++)
                {
                    m_walls[r, c] = false;

                    // If the list contains something unwalkable, then it must be a wall (true).
                    foreach (Terrain t in terrainGrid[r, c])
                        if (m_unwalkableTerrain.Contains(t))
                            m_walls[r, c] = true;
                }
            }

            // Build the graph based on our current walls.
            m_graph = new Node[m_rows, m_columns];

            for (int r = 0; r < m_rows; r++)
            {
                for (int c = 0; c < m_columns; c++)
                {
                    m_graph[r, c] = null;

                    // So long as our current position is not a wall, add it to the graph.
                    if (!IsWall(r, c))
                        AddNode(r, c);
                }
            }
        }

        public bool IsWall(int r, int c)
        {
            // So long as the desired (r, c) coordinate exists in the 2D array, return the value.
            if (PointExists(r, c))
                return m_walls[r, c];

            // If that value does not exist, return true that it's a wall.
            return true;
        }

        /// <summary>
        /// Permanently adds a wall to the (row, column) position of the path-finding grid.
        /// 
        /// Use AddToWallMap(int row, int column, int lifeTime) to temporarily add a wall.
        /// </summary>
        /// <param name="row">The row of the wall to be added.</param>
        /// <param name="column">The column of the wall to be added.</param>
        public void AddToWallMap(int row, int column)
        {
            if (PointExists(row, column))
            {
                RemoveNode(row, column);
                m_walls[row, column] = true;
            }
        }

        /// <summary>
        /// Permanently removes a wall from the (row, column) position of the path-finding grid.
        /// 
        /// Use RemoveFromWallMap(int row, int column, int lifeTime) to temporarily remove a wall.
        /// </summary>
        /// <param name="row">The row of the wall to be added.</param>
        /// <param name="column">The column of the wall to be added.</param>
        public void RemoveFromWallMap(int row, int column)
        {
            if (PointExists(row, column))
            {
                AddNode(row, column);
                m_walls[row, column] = false;
            }
        }

        /// <summary>
        /// Gets the list of tiles (as Points on the grid) for a path from one tile to another.
        /// </summary>
        /// <param name="startTile">The tile, in grid coordinates, where the path starts</param>
        /// <param name="endTile">The tile, in grid coordinates where the path ends (the destination)</param>
        /// <returns>Returns a list of Points that are grid positions for the tiles needed to walk to reach the
        /// destination tile.  Returns null if either the start or end tile is invalid or if the path does not exist.  The
        /// Point list will NOT include the start tile but does include the end tile.</returns>
        public List<Point> GetPath(Point startTile, Point endTile)
        {
            Node startNode = GetNodeAt(startTile.X, startTile.Y);
            Node endNode = GetNodeAt(endTile.X, endTile.Y);

            // If the start or end tile has no node (which will happen when it is a wall)
            // then just return null
            if (startNode == null || endNode == null)
            {
                return null;
            }

            // Do A* searching to find the shortest path to the target tile
            int currentDistance = 0;

            // Reset all the nodes
            foreach (Node node in m_graph)
            {
                if (node != null)
                {
                    node.Previous = null;
                    node.Distance = int.MaxValue;
                }
            }

            // Create a new queue to hold the nodes to be searched and set its function used for comparing
            PriorityQueue<Node, float> searchQueue = new PriorityQueue<Node, float>(CompareNodes);

            // Start off at the start node
            startNode.Distance = 0;
            startNode.Previous = startNode;
            searchQueue.Enqueue(startNode, 0);

            // Keep track of whether the end node has been found
            bool hasReachedEndNode = false;

            // While there are nodes to search, keep adding the neighbors
            while (searchQueue.Count > 0 && !hasReachedEndNode)
            {
                currentDistance++;

                Node currentNode = searchQueue.Dequeue().Value;

                // Go through all the current node's neighbors
                foreach (Node node in currentNode.Neighbors)
                {
                    // Only add nodes that have no previous node assigned to avoid readding the
                    // same node over and over again
                    if (node.Previous == null)
                    {
                        node.Distance = currentDistance;
                        node.Previous = currentNode;

                        if (node.Row == endNode.Row && node.Column == endNode.Column)
                        {
                            hasReachedEndNode = true;
                            break;
                        }

                        float distanceToEnd = new Vector2(node.Row - endNode.Row, node.Column - endNode.Column).Length();

                        // Enqueue the new node with the current distance plus the distance to the end node (A*)
                        searchQueue.Enqueue(node, currentDistance + distanceToEnd);
                    }
                }
            }

            // If the end node was not found, there is no path to it from the beginning node so return null
            if (!hasReachedEndNode)
            {
                return null;
            }

            // Otherwise, get the path and return it
            List<Point> tileList = new List<Point>();

            Node pathNode = endNode;

            // Go backwards from the end node until you reach the start node
            while (pathNode != startNode)
            {
                tileList.Add(new Point(pathNode.Row, pathNode.Column));
                pathNode = pathNode.Previous;
            }

            // Reverse the list to get the correct ordering
            tileList.Reverse();

            return tileList;
        }

        #region Graph/Node Functions

        private Node GetNodeAt(int row, int column)
        {
            if (PointExists(row, column) && m_graph[row, column] != null)
                return m_graph[row, column];

            return null;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="row"></param>
        /// <param name="column"></param>
        /// <returns>True if the Node did not exist and was created.</returns>
        private bool AddNode(int row, int column)
        {
            Node n = GetNodeAt(row, column);

            // Make sure the row and column are in range and the Node does not exist.
            if (n == null)
            {
                m_graph[row, column] = new Node(row, column);
                Node currentNode = m_graph[row, column];

                List<Node> neighbors = new List<Node>();
                neighbors.Add(GetNodeAt(row - 1, column - 1));  // upper left
                neighbors.Add(GetNodeAt(row - 1, column));    // upper
                neighbors.Add(GetNodeAt(row - 1, column + 1));   // upper right
                neighbors.Add(GetNodeAt(row, column - 1)); // left
                neighbors.Add(GetNodeAt(row, column + 1));    // right
                neighbors.Add(GetNodeAt(row + 1, column - 1));    // lower left
                neighbors.Add(GetNodeAt(row + 1, column));    // lower
                neighbors.Add(GetNodeAt(row + 1, column + 1));   // lower right

                foreach (Node neighbor in neighbors)
                {
                    if (neighbor != null)
                    {
                        currentNode.AddNeighbor(neighbor);
                        neighbor.AddNeighbor(currentNode);
                    }
                }

                return true;
            }

            return false;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="row"></param>
        /// <param name="column"></param>
        /// <returns>True if the Node existed and was removed.</returns>
        private bool RemoveNode(int row, int column)
        {
            Node n = GetNodeAt(row, column);

            // Make sure the row and column are in range and the Node exists.
            if (n != null)
            {
                foreach (Node neighbor in n.Neighbors)
                    neighbor.Neighbors.Remove(n);

                m_graph[row, column] = null;

                return true;
            }

            return false;
        }

        /// <summary>
        /// Compares 2 nodes to see which one has higher priority.  The one with the LOWER number
        /// has higher priority in this case.
        /// </summary>
        /// <param name="left">The first priority value.</param>
        /// <param name="right">The second priority value.</param>
        /// <returns>Returns -1 if left has higher priority, 1 if right has higher priority and 0 if they have the same priority.</returns>
        private int CompareNodes(float left, float right)
        {
            if (left > right)
            {
                return -1;
            }
            else if (left < right)
            {
                return 1;
            }

            return 0;
        }

        #endregion

        #endregion

        #region Node Class

        private class Node
        {
            public int Distance;    // Distance from start node
            public Node Previous;   // Previous node in the distance chain
            public List<Node> Neighbors;    // Connected nodes
            public int Row, Column; // Position of this node

            public Node(int row, int column)
            {
                Row = row;
                Column = column;

                Distance = int.MaxValue;
                Previous = null;
                Neighbors = new List<Node>();
            }

            public void AddNeighbor(Node node)
            {
                Neighbors.Add(node);
            }

            public void RemoveNeighbor(Node node)
            {
                Neighbors.Remove(node);
            }

            public override string ToString()
            {
                return "Row: " + Row + "\n" +
                       "Column: " + Column + "\n" +
                       "Distance: " + Distance;
            }
        }

        #endregion
    }
}